package com.suxin.algorithm.tree.binary;

/**
 * @author Tang
 * @classname SearchTree
 * @description [  ]
 * @date 2022/10/27 22:18
 */
public class SearchTree {

    /**
     * 左小 右大
     * @param root
     * @param node
     */
    public static void insert(Node<Integer> root, Node<Integer> node) {
        if (root == null) {
            return;
        }
        // 根结点的数据 < 新结点的数据
        if (root.getData() < node.getData()) {
            // 向右边递归
            if (root.getRight() != null) {
                insert(root.getRight(), node);
            }else {
                // 一直到右边的叶子结点，直接设置为叶子结点
                root.setRight(node);
            }
        } else {
            // 向左边递归
            if (root.getLeft() != null) {
                insert(root.getLeft(), node);
            }else {
                // 一直到左边的叶子结点，直接设置为叶子结点
                root.setLeft(node);
            }
        }
    }

    public static void search(Node<Integer> root, Integer number) {
        if (root == null) {
            return;
        }
        if (root.getData().equals(number)) {
            System.out.println("找到了要搜索的数字:" + number);
            return;
        }
        // 左子树搜索
        if (root.getData() >= number) {
            search(root.getLeft(),number);
        } else {
            // 右子树搜索
            search(root.getRight(),number);
        }
    }

    public static Node<Integer> delNode(Node<Integer> root,Node<Integer> preNode, Integer number) {
        Node<Integer> pre = null,oldRoot = root;
        // 要删除的节点是root节点
        if (root.getLeft() != null && root.getRight() != null) {
            if (root.getData().equals(number)) {
                // 去右子树，最左边的节点，进行删除
                root = root.getRight();
                while (root.getLeft() != null) {
                    pre = root;
                    root = root.getLeft();
                }
                if (pre != null) {
                    pre.setLeft(null);
                }
                oldRoot = root;
                oldRoot.setData(root.getData());
                return oldRoot;
            }else {
                //
                while (root != null) {
                    if (root.getData().equals(number)) {
                        break;
                    }
                    if (root.getData() > number) {
                        root = root.getLeft();
                    }else {
                        root = root.getRight();
                    }
                }
            }
        }
        // 左子树
        if (root.getLeft() != null && root.getData() > number) {

        }
        // 右子树
        if (root.getRight() != null && root.getData() < number) {

        }
        return root;
    }

    public static void main(String[] args) {
        Node<Integer> rootNode = new Node<>(20,null,null);
        Node<Integer> Node1 = new Node<>(10,null,null);
        Node<Integer> Node2 = new Node<>(5,null,null);
        Node<Integer> Node3 = new Node<>(8,null,null);
        Node<Integer> Node4 = new Node<>(9,null,null);
        Node<Integer> Node5 = new Node<>(4,null,null);
        Node<Integer> Node6 = new Node<>(40,null,null);
        Node<Integer> Node7 = new Node<>(23,null,null);
        Node<Integer> Node8 = new Node<>(45,null,null);
        insert(rootNode,Node1);
        insert(rootNode,Node2);
        insert(rootNode,Node3);
        insert(rootNode,Node4);
        insert(rootNode,Node5);
        insert(rootNode,Node6);
        insert(rootNode,Node7);
        insert(rootNode,Node8);
        TreePrint.centerPrint(rootNode);
        System.out.println();
        search(rootNode, 19);
    }

}
